1. Field of the Invention
The present invention relates to performance analysis of logic circuits, and more particularly, to a system for efficiently performing chip-level timing analysis in a latch-based logic design.
2. Description of the Related Art
Timing verification techniques are useful for determining whether a sequential circuit will run correctly under a given clock schedule. To make this determination, it is necessary to accurately model the timing performance of each of the circuit's components. All possible paths through the circuit must be analyzed to guarantee compatibility with data and clock timing. An identification of critical paths, i.e., those paths through the circuit that place the tightest constraints on the circuit's timing behavior, is of particular interest to designers who wish to identify why the circuit fails to meet a desired timing schedule.
While the concept of a critical path has been used for many years to analyze both combinatorial and sequential circuits, these analyses assume that storage elements are edge-triggered. If instead, a circuit includes level-sensitive latches, simplifications associated with edge-triggered device analysis break down. Recent work has extended the classical definition of critical path to better account for the timing properties of level sensitive latches. See e.g., T. M. Burks, K. A. Sakallah, and T. N. Mudge, Critical Paths in Circuits with Level-Sensitive Latches, IEEE TRANSACTIONS OF VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, Vol. 3, No. 2, June 1995 at 273.
Level-sensitive latches, like edge-triggered "flip-flops," are sequential circuit elements; i.e., they are used to sample and store state at various points in a logic design. An ideal, edge-triggered flip-flop samples state at either the rising or falling edge of its enable signal, then maintains this value until the next triggering edge. A level-sensitive latch, on the other hand, follows the value of its data input whenever the enable is active. A level-sensitive latch is said to be "transparent" while its enable is active. When the enable transitions to inactive, the value of the input at that time is maintained.
It is a relatively simple problem to identify stages (sequential element to sequential element) which cause a circuit designed with edge-triggered state elements to fail. In particular, any combinational path which delivers data to state elements after the triggering edge is a failure. However, the problem is more complex for a circuit which includes level-sensitive latches. In particular, level-sensitive latches allow "borrowing" to occur between neighboring stages of combinational logic. When data arrives at a latch during the transparent phase, it flows immediately through to the next combinational stage. Thus a long stage can borrow time from a subsequent short stage, up to the end of the active phase of the latch enable. While such borrowing provides the logic designer with significantly more flexibility, it complicates the problem of timing analysis, as the number of adjacent stages which contributing to a critical path varies. Borrowing results in the linking (for purposes of timing analysis) of different numbers of stages along different paths to (or through) a particular circuit element. Furthermore, as operating frequency changes, the number of linked stages along a particular path changes.
In addition to the analytic complexity added by borrowing, the computational complexity (i.e., scaling) of the critical path search problem can make straightforward computational implementations intractable for large complex circuits. In general, the topology of a graph representation of the circuit of interest must be known to determine the computational complexity. Two characteristic parameters of the graph of a circuit, the average fanout or branching factor, B, and the average path length or depth, D, are important indicators of the computational complexity of the search. Running of a depth-first search is then O(B.sup.D). For a complex microprocessor with a fanout of 15 and average path length of 20, 3.33.times.10.sup.23 paths flow from a single starting point. A straightforward computational implementation of the depth-first search problem would have to save and analyze each such path.